#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

bool isValid(string s) {
    unordered_map<char, char> p = {{')', '('}, {']', '['}, {'}', '{'}};
    stack<int> st;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '[' || s[i] == '(' || s[i] == '{')
            st.push(s[i]);
        else if (st.empty() || st.top() != p[s[i]])
            return 0;
        else
            st.pop();
    }
    if (!st.empty()) return 0;
    return 1;
}